package com.jojo.elementary.day4_array;

import java.util.ArrayList;
import java.util.List;

/**
 * 118、杨辉三角
 *
 * 给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
 * 在「杨辉三角」中，每个数是它左上方和右上方的数的和。
 *
 * 示例 1:
 * 输入: numRows = 5
 * 输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
 *
 * 示例2:
 * 输入: numRows = 1
 * 输出: [[1]]
 *
 */
public class YhTriangle {

    /** myCode 使用二维数组 */
    public List<List<Integer>> generate(int numRows) {
        int[][] arr = new int[numRows][numRows];
        arr[0][0] = 1;
        if(numRows > 1){
            for (int i = 1;i < numRows;i++){
                for (int j = 0;j <= i;j++){
                    if(j >= 1){
                        arr[i][j] = arr[i - 1][j - 1] + arr[i - 1][j];
                    }else {
                        arr[i][j] = arr[i - 1][j];
                    }
                }
            }
        }
        List<List<Integer>> lists = new ArrayList<>();
        for (int[] ints : arr) {
            List<Integer> list = new ArrayList<>();
            for (int anInt : ints) {
                if (anInt != 0){
                    list.add(anInt);
                }
            }
            lists.add(list);
        }
        return lists;
    }

    /** pe. 直接用list */
    public List<List<Integer>> generate2(int numRows) {
        List<List<Integer>> lists = new ArrayList<>();
        for (int i = 0;i < numRows;i++){
            List<Integer> list = new ArrayList<>();
            for (int j = 0;j <= i;j++){
                if (j == 0 || j == i){
                    list.add(1);
                }else{
                    list.add(lists.get(i - 1).get(j - 1) + lists.get(i - 1).get(j));
                }
            }
            lists.add(list);
        }
        return lists;
    }

    public static void main(String[] args) {
        YhTriangle yh = new YhTriangle();
        List<List<Integer>> generate = yh.generate2(5);
        System.out.println(generate.toString());
    }
}
